class Solution {
public:
    int countPrimes(int n) {
        if (n <= 2)
            return 0;
        vector<bool> visit(n + 5, false);
        vector<int> Prime;

        for (int i = 2; i < n; i++)
        {
            if (!visit[i])
                Prime.push_back(i);
            for (int j = 0; j < Prime.size(); j++)
            {
                if (i * Prime[j] > n)
                    break;
                visit[i * Prime[j]] = true;
                if (i % Prime[j] == 0)
                    break;
            }

        }

        return Prime.size();
    }
};